package com.wk.arth.od;

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

/**
 * 寻找链表中间节点
 * 输入：
 * 每个测试用例第 1 行给出链表首结点的地址、结点总个数正整数 N (≤105)。结点的地址是 5
 * 位非负整数，NULL 地址用−1 表示。
 * 接下来有 N 行，每行格式为：
 * Address Data Next
 * 其中 Address 是结点地址，Data 是该结点保存的整数数据(0 ≤ Data ≤ 108)，Next
 * 是下一结点的地址。
 * 输出：
 * 在一行中输出 L中间结点保存的数据。如果有两个中间结点，则输出第二个中间结点保存的数据
 *
 * 00010 5
 * 00000 3 00001
 * 00010 5 12309
 * 11451 6 00000
 * 12309 7 11451
 * 00001 8 -1
 *
 * ==> 6
 * @author wukai
 * @date 2023/4/19 11:26
 */
public class Link_Mid_Node {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String line = scanner.nextLine();
        String[] list = line.split("\\s+");
        String adr1 = list[0];
        int n = Integer.parseInt(list[1]);
        int mid = n/2;
        Map<String,Integer> map = new HashMap<>();
        String[][] link = new String[n][3];
        for (int i = 0;i<n;i++){
            String node = scanner.nextLine();
            String[] nodeArr = node.split("\\s+");
            link[i] = nodeArr;
            map.put(nodeArr[0],i);
        }
        int i =0;
        String curAdr = adr1;
        while (i < mid){
            int index = map.get(curAdr);
            curAdr = link[index][2];
            i++;
        }
        System.out.println(link[map.get(curAdr)][1]);
    }
}
